class Solution {
    public boolean canPartition(int[] nums) {
        int result=0;
        for (int i = 0; i < nums.length; i++) {
            result+=nums[i];
        }
        if(result%2==1) return false;
        int n=result/2;
        int[] dp=new int[n+1];
        for (int i = 1; i <nums.length ; i++) {
            for (int j = n; j>=nums[i] ; j--) {
                dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        return dp[n]==n;


    }
}

//runtime:24 ms
//memory:39.9 MB
